1. Field of the Invention
The present invention generally relates to methods and apparatus for decoding error correcting codes, and, more particularly, relates to methods and apparatus for determining error locator polynomials and error evaluator polynomials in the process of decoding error correcting codes.
2. Description of the Prior Art
In the transmission of data from a source location to a destination location through a variety of media, noise caused by the transmission path and/or the media itself causes errors in the transmitted data. Thus, the data transmitted is not the same as the data received. In order to determine the errors in the received data, various methods and techniques have been developed to detect and correct the errors in the received data. One of the methods is to generate a codeword which includes a message part (data to be transmitted) and a parity part (information for performing error correction).
In this context and in one form, codewords are generated from encoding operations performed upon the original data comprising of symbols to yield an encoded word (codeword) of information having N symbols where the first K symbols are message symbols and the subsequent N-K symbols are parity symbols. The encoded redundancy in the form of N-K parity symbols is then available during the decoding operation to detect and correct errors in the codeword (for all N symbols) up to some limit or merely to detect errors up to some larger limit.
Among the most well-known error-correcting codes, the BCH (Bose-Chaudhuri-Hocquenghen) codes and the Reed-Solomon (RS) codes are the most widely used block codes in the communication field and storage systems. The mathematical basis of BCH and RS codes is explained by: E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968; and S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications, Prentice-Hall, Englewood Cliffs, N.J., 1983.
An (N, K) BCH or RS code has K message symbols and N coded symbols, where each symbol belongs to GF(q) for a BCH code or GF(q.sup.m) for a RS code. A binary (N,K) BCH code can correct up to t errors with N=2.sup.m 1, N-K&lt;=mt. An (N, K) RS code can correct t errors and .rho. erasures with 2t+.rho.&lt;=N-K. For binary BCH codes, an error can be corrected simply by finding out the error location. For RS codes, an error can be corrected by finding out the error location and the error value. In RS codes, an erasure is defined to be an error with a known error location, and hence its correction reduces to finding the error value.
The method steps for common popular RS decoder architectures for the correction of errors can be summarized into four steps: (1) calculating the syndromes from the received codewords, (2) computing the error locator polynomial and the error evaluator polynomial, (3) finding the error locations, and (4) computing the error values. If both errors and erasures and corrected (defined as errata), the four steps are modified to: (1) calculating the syndromes and Forney syndromes from the received codewords and the erasure locations, (2) computing the errata locator polynomial and the errata evaluator polynomial, (3) finding the errata locations, and (4) computing the errata values.
Referring to FIG. 1a, the general decoding steps are illustrated. The received data, R(x), is provided to a syndrome generator 10 to generate a syndrome polynomial, S(x), representing the error pattern of the codeword from which the errors can be corrected. The syndromes depend only on the error pattern (which is part of the syndrome) and not on the transmitted codeword. The syndromes are then provided to a key equation solver 12 using a well-known Berlekamp-Massey algorithm to generate an error locator polynomial, .sigma.(x), and an error evaluator polynomial, .OMEGA.(x). The error locator polynomial indicates the location(s) of the error and the error evaluator polynomial indicates the value(s) of the error. In the next step, the error locator polynomial is passed to a Chien search engine 14 to generate the root(s), .beta..sub.l.sup.-1, indicating the location(s) of the errors. The error value evaluator 16, receiving the root(s) and the error evaluator polynomial, .OMEGA.(x), generates the error value(s) corresponding to the root(s).
In the implementation of the key equation solver (step 2 above), the step involves solving the key equation which is EQU S(x).sigma.(x)=.OMEGA.(x) mod x.sup.N-K
where S(x) is the syndrome polynomial, .sigma.(x) is the error locator polynomial and .OMEGA.(x) is the error evaluator polynomial. When both errors and erasures are corrected, .sigma.(x) and .OMEGA.(x) are the errata locator polynomial and the errata evaluator polynomial, respectively. When both errors and erasures are corrected, .sigma.(x)=.lambda.(x).LAMBDA.(x), where .lambda.(x) and .LAMBDA.(x) each corresponds to the error locator polynomial and the erasure locator polynomial, respectively. FIG. 1b illustrates the general processing steps for the errata correction . The syndrome calculator 20 receives not only R(x) but also erasure data and generates the syndrome polynomial S(x) and the Forney syndrome polynomial T(x). The key equation solver 22 processes S(x) and T(x) to generate the errata evaluator polynomial, .OMEGA.(x), and the errata locator polynomial, .sigma.(x). The errata locator polynomial is provided to a Chien search engine 24 to determine the locations of the errors, while both the errata evaluator polynomial and errata locations are provided to an errata value evaluator to generate the errata values.
The techniques frequently used to solve the key equation include the Berlekamp-Massey algorithm, the Euclidean algorithm, and the continuous-fraction algorithm. Compared to the other two algorithms, the Berlekamp-Massey algorithm is generally considered to be the one with the smallest hardware complexity. The detailed description of the Berlekamp-Massey algorithm is explained in Chapter 7 of the Berlekamp reference cited above and the article by J. L. Massey, Shift-Register Synthesis and BCH Decoding, IEEE Transaction on Information Theory, IT-15:122-127, 1969. An inversionless Berlekamp-Massey algorithm was proposed by Burton to eliminate the costly finite-field inverters (FFIs). H. O. Burton, Inversionless Decoding of Binary BCH Codes, IEEE Transaction on Information Theory, IT-17:464-466, 1971.
Prior art technologies applied the traditional Berlekamp-Massy algorithm (or variation thereof) for the calculation of the error locator polynomial and the error evaluator polynomial, and designed circuits based upon these algorithms. However, each of these algorithms require a large number of finite-field multipliers (FFM) and perhaps a finite-field inverters (FFI). Each of the FFM's and FFI's translates into a hardware circuitry and real estate on an integrated circuit chip. Therefore, the goal here is to derive a method for solving of the polynomials in an efficient manner and to minimize the amount of circuitry required in the implementation of the algorithm. The number of FFM's and FFI's is typically a function of the variable t, which is a function of (N-k)/2. Table 1 illustrates the authors of the algorithms and the corresponding number of FFM's and FFI's for t equals
TABLE 1 ______________________________________ FFM's as a Reference function of t FFM's FFI's ______________________________________ Berlekamp 3t 24 1 Liu 2t - 1 17 1 Oh 2t 16 1 Reed 3(t + 1) 27 0 ______________________________________
As is listed in Table 1 in reference to error correction only (not errata), one implementation of the traditional Berlekamp-Massey algorithm (Berlekamp, U.S. Pat. No. 4,162,480) requires 3t or 24 FFM's and 1 FFI. In the article Architecture for VLSI Design of Reed-Solomon Decoders, IEEE Transactions on Computers, Vol. c-33, No. 2, February 1984, Liu demonstrated an algorithm requiring 2t-1 or 17 FFM's and 1 FFI. In U.S. Pat. No. 5,583,499, Oh et al. disclosed a circuitry requiring 2t or 16 FFM's and 1 FFI.
On the other hand, Reed et al. have shown that for algorithms where inversion is not required, the relatively complex FFI circuitry is not required as well. VLSI Design of Inverse-Free Berlekamp-Massey Algorithm, Reed, Shih, and Truong, IEE Proceedings-E, Vol. 138, No. 5, September 1991. However, although Reed's algorithm demonstrated the elimination of the FFI, the resulting algorithm required a greater number of FFM's, beyond 3t! For errata correction, the number of FFM's required are even higher, usually 2 times of the case for error correction.
Therefore, it would be desirable to have an inversionless method and apparatus that requires no FFIs and minimizes the number of FFMs in the implementation thereof.